// 给定一个数组nums，元素值只有0,1,2，分别代表红色，白色，蓝色，将数组排序，使得红色在前，白色在中间，蓝色在最后
// 使用常数空间，一趟扫描解决

// 思路，双指针 + 快速排序 思路
// 定义两个指针left和right，分别指向数组的头部和尾部，left表示处理好的红色元素的尾部，right表示处理好的蓝色的头部
// 使用index遍历数组，如果遇到0，则交换left和index的元素，同时left++,如果遇到2，则交换right和index的元素，同时right--
// 直到index移动到right位置

function sortColors(nums) {
    let left = 0
    let right = nums.length - 1
    let index = 0
    while (index <= right) {
        // 这一句不能少，出现这种情况需要更新index，left前面都是整理好的，index
        if (index < left) {
            index += 1
        } else if(nums[index] === 0) {
            [nums[left], nums[index]] = [nums[index], nums[left]];
            left++

        } else if (nums[index] === 2) {
            [nums[right], nums[index]] = [nums[index], nums[right]];
            right--
        } else {
            index++
        }
    }
}


function sortColors2(nums) {
    let left = 0
    let right = nums.length - 1
    let index = 0
    while (index <= right) {
        if(nums[index] === 0) {
            [nums[left], nums[index]] = [nums[index], nums[left]];
            left++
            index++
        } else if (nums[index] === 2) {
            [nums[right], nums[index]] = [nums[index], nums[right]];
            right--
        } else {
            index++
        }
    }
}

let arr = [2, 0, 2, 1, 1, 0]
// sortColors(arr)
console.log(arr)
